A common problem in image processing is to find primitives such as lines, curves, circles and ellipses in frames of image data. One approach is to use a Hough transform. The Hough transform maps a point in the image to a curve in the transform domain that indicates the parameters of all primitives passing through the point. If the primitive is a straight line, the Hough transform of the entire image is mathematically equivalent to a 2-dimensional discrete Radon transform or a Slant Stack transform. However, when computing a 2-dimensional discrete Radon transform or a Slant Stack transform it is usual to calculate the transform value at each point in the transform domain from a set of points in the image array.
Calculation of the transform is computationally expensive. This presents problem for applications where rapid computation is required at a low cost. An example is the analysis of video frames from an automobile video camera, for applications such as vehicle guidance and license-plate reading. Another example is computer vision for robots. All of these applications require real-time processing of video frames.
Prior applications in this area have focused mainly on the design of algorithms for implementation on general-purpose processors, such as personal computers, digital signal processors or general-purpose image processors.
Custom hardware has been proposed for analyzing a Hough transform.
The Hough transform requires mapping a point in the image to a curve in the transform array. There are two approaches to the computation of the Hough transform. The first approach is to use a large number of accumulators, one for each point in the transform array. This approach results in complex hardware, such as computer graphics cards. The second approach is to use a single accumulator and to store the transform array in a memory. This approach is slow because of the requirement to perform multiple read and write operations for each image point to move partial sums between the memory and the accumulator.